@file:Suppress("NULLABILITY_MISMATCH_BASED_ON_JAVA_ANNOTATIONS")

package tree

import java.util.*

/**
 *
 *                 1
 *             2        3
 *          4     5       6
 *              7  8
 *
 *
 *preOrder:  1  2  4  5  7  8  3  6 
 *inOrder:   4  2  7  5  8  1  3  6
 *postOrder: 4  7  8  5  2  6  3  1
 *traverse：     1  2  3  4  5  6  7  8
 *
 *
 *
 *
 */

val treeRoot = TreeNode(
        "1",
        TreeNode(
                "2",
                TreeNode(
                        "4",
                        null,
                        null
                ),
                TreeNode("5",
                        TreeNode("7",
                                null,
                                null),
                        TreeNode("8",
                                null,
                                null))
        ),
        TreeNode("3",
                null,
                TreeNode("6",
                        null,
                        null))
)

val tree1 = TreeNode(
        "2",
        TreeNode(
                "3",
                TreeNode("1",
                        null,
                        null),
                null),
        null)

fun main(args: Array<String>) {

//    preorder(treeRoot)
//    println()
    preOrder1(treeRoot)
//    preOrder2(treeRoot)


//    println("\n-----------中序 inOrder-----------")
//    inOrder1(treeRoot)
    println()

    voidOrder(treeRoot)
//
//    println("\n-------------------层次-------------")

//
//
//    println("-----------------------后序postOrder--------------------")
//    postOrder(treeRoot)
//    postOrder1(treeRoot)
}

fun preorder(root: TreeNode?) {

    //当前节点不空，打印当前节点，否则出栈
    //不然继续压栈左右
    if (root != null) {
        print(root.value + "  ")
        preorder(root.left)
        preorder(root.right)
    }
}

fun preOrder1(root: TreeNode?) {
    val stack = Stack<TreeNode?>()

    stack.push(root)
    while (stack.isNotEmpty()) {
        val node = stack.pop()
        if (node != null)
            print(node.value + "  ")

        //根左右，所以先压栈右子树，
        if (node?.right != null)
            stack.push(node.right)
        if (node?.left != null)
            stack.push(node.left)
    }


}


/**
 * 中序遍历
 *  左根右.顺序，所以先左边的节点入栈，直到左节点没有以后，出栈则是根节点，打印出来
 *
 *  /**
 *                 1
 *             2        3
 *          4     5       6
 *              7  8
 *
*/

4  2  7  5  8  1  3  6
先访问左子树，再访问根节点，最后右子树

遍历左子树的思路就是 先一路找到左边最下面的节点
最后还要回过头来根据根节点来访问右子树，所以每次需要把 节点入栈



 实际上中序可以看作是前序的一种特例，实际上都是左边然后右边

 而后序是完全不同的，是割裂开的
 */

fun voidOrder(root: TreeNode) {

    val stack = ArrayDeque<TreeNode>()

    var curr: TreeNode? = root

    while (curr != null || stack.isNotEmpty()) {

        while (curr != null) {

            stack.push(curr)
            curr = curr.left
        }

        //此时左边访问完成,出栈根节点，打印，访问右子树

        curr = stack.pop()

        print(curr.value + "  ")

        curr = curr.right
    }

}

/**

 *
 *                 1
 *             2        3
 *          4     5       6
 *              7  8
 *
 *4  7  8  5  2  6  3  1
 */


fun postOrder(root: TreeNode) {

    val stack = ArrayDeque<TreeNode?>()

    var curr: TreeNode? = root

    while (curr != null || stack.isNotEmpty()) {

        while (curr != null) {
            stack.push(curr)
            curr = curr.left
        }

        //弹出左节点
        curr = stack.pop()

        //访问左节点
        print(curr?.value + "  ")

        if (curr?.right != null) {
            curr = curr.right
            stack.push(curr?.right)
        }else{


        }

    }
}

